package targetOffer;

import java.util.ArrayList;

public class Algorithm {
    /**
     * 一维数组二分查找
     *
     * @param array
     * @param target
     * @param start
     * @param end
     * @return 如果数组有target，返回数的索引，否则返回最后一个小于target的元素的索引
     */

    public static int binarySearch(int[] array, int target, int start, int end) {
        int i = (start + end) / 2;
        if (array[i] == target || start > end) {
            return i;
        } else if (array[i] > target) {
            return binarySearch(array, target, start, i - 1);
        } else {
            return binarySearch(array, target, i + 1, end);
        }
    }

    /**
     * 在二维数组中就行二分查找，要求该二维数组是每行递增，每列递增
     *
     * @param array
     * @param target
     * @param startX
     * @param endX
     * @param startY
     * @param endY
     * @return
     */

    public static boolean binarySearchIn2DArray(int[][] array, int target, int startX, int endX, int startY, int endY) {
        if (startX > endX || startY > endY) {
            return false;
        }
        int x = (startX + endX) / 2;
        int result = binarySearch(array[x], target, startY, endY);
        if (array[x][result] == target) {
            return true;
        }
        return binarySearchIn2DArray(array, target, startX, x - 1, result + 1, endY)
                || binarySearchIn2DArray(array, target, x + 1, endX, startY, result);
    }

    /**
     * 替换str中orginal字符为holder
     *
     * @param str
     * @param original
     * @param holder
     * @return
     */
    public static String replace(String str, char original, String holder) {
        final int n = str.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            final char c = str.charAt(i);
            if (c == original) {
                sb.append(holder);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    /**
     * 反序遍历一个链表
     *
     * @param node
     * @param list
     * @return
     */
    public static ArrayList<Integer> parseListFromTailToHead(ListNode node, ArrayList<Integer> list) {
        if (node != null) {
            parseListFromTailToHead(node.next, list);
            list.add(node.val);
        }
        return list;
    }

    /**
     * 在一个无序的数组的寻找target，如果有返回其下标，否则返回-1
     *
     * @param array
     * @param target
     * @return
     */
    public static int findIndex(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode node = new TreeNode(pre[preStart]);
        final int index = Algorithm.findIndex(in, node.val);
        int leftNumber = index - inStart; // 左子树有多少个节点
        node.left = Algorithm.buildTree(pre, preStart + 1, preStart + leftNumber, in, inStart, index - 1);
        node.right = Algorithm.buildTree(pre, preStart + leftNumber + 1, preEnd, in, index + 1, inEnd);
        return node;
    }


    /**
     * 树的先序遍历
     * @param node
     */
    public static void preTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val);
        preTraverse(node.left);
        preTraverse(node.right);
    }

    /**
     * 树的中序遍历
     * @param node
     */
    public static void inTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        inTraverse(node.left);
        System.out.print(node.val);
        inTraverse(node.right);
    }

    /**
     * 树的后序遍历
     * @param node
     */
    public static void postTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        postTraverse(node.left);
        postTraverse(node.right);
        System.out.print(node.val);
    }

    public static int pow(int base, int exp) {
        if (exp == 1) {
            return 1;
        } else {
            int result = 1;
            while (exp > 0) {
                result *= base;
                exp--;
            }
            return result;
        }
    }
}
